

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if dividend == 0:
            return 0

        same_symbol = True if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0) else False
        dividend = dividend if dividend > 0 else -dividend
        divisor = divisor if divisor > 0 else -divisor
        result = list()

        while divisor <= dividend:
            k, dividend = self.get_k(dividend, divisor)
            result.append(k)
        result = sum(result)
        result = result if same_symbol else -result

        return min(max(-2147483648, result), 2147483647)


    @staticmethod
    def get_k(dividend, divisor):
        k = 0
        while True:
            temp = divisor << k
            if temp > dividend:
                return 2**(k-1), dividend - (divisor << (k-1))
            if temp == dividend:
                return 2**k, 0

            k += 1

    def divide2(self, dividend, divisor):
        positive = (dividend > 0) is (divisor > 0)
        dividend, divisor = abs(dividend), abs(divisor)

        result = self.compute(dividend, divisor)

        if not positive:
            result = -result

        return min(max(-2147483648, result), 2147483647)

    def compute(self, dividend, divisor):
        result = 0
        while divisor <= dividend:
            temp, i = divisor, 1
            while temp <= dividend:
                dividend -= temp
                result += i
                i <<= 1
                temp <<= 1
        return result

if __name__ == '__main__':
    s = Solution()
    print s.divide(-2147483648, -1)
    print s.divide2(-2147483648, -1)
